I. Field of the Invention
The present invention relates to data communications. More particularly, the present invention relates to a novel and improved communication system employing concatenated coding.
II. Description of the Related Art
With the advent of digital communications and the need to transmit large amount of data through an impaired and bandlimited channel, the need for coding of digital data to facilitate correct data reception is of great significance. Data transmissions are typically hindered by impairments in the transmission channel, namely additive noise and spurious signals within the transmission bandwidth. The transmit power is limited by practical considerations and the transmitted signal is attenuated by the path loss and may be distorted by other phenomenon, such as multipath, before it reaches the receiver. The design of a digital communications system entails the determination of the worse case signal quality at which the receiver is expected to operate. This signal quality is measured as an energy-per-bit-to-noise ratio (Eb/No) and is determined by the transmitted power, path loss, and noise and interference. The minimum Eb/No which yields the desired level of performance is considered the system threshold level.
At the threshold level, the probability of error (PE) for any digital transmission scheme such as binary shift keying (BPSK), quaternary phase shift keying (QPSK), or quadrature amplitude modulation (QAM) can be calculated. Typically the PE of the selected transmission scheme is not adequate for the application. Improvement in the PE is achieved by encoding the digital data before transmission and decoding the data at the receiver. The coding scheme is determined by the requirements of the application and the channel characteristic. Coding allows for detection and correction of errors in the transmitted data at the expense of a lower effective data rate.
Two classes of coding, block coding and convolutional coding, are utilized to improve PE. Convolutional code provides good error correcting capability but typically outputs correlated bursts of error. Also, the Viterbi decoder supports the use of soft decisions to improve performance with minimal increase in hardware complexity. Block codes have built in burst error handling capability when combined with the proper level of interleaving. In fact, a single error correcting Reed-Solomon block code could handle any burst of errors within a single symbol. When convolutional coding alone would not produce the required coding gain, a concatenated code comprising a convolutional code and a block code can be used.
A Reed-Solomon code is a powerful non-binary, cyclic, and linear block code that achieves the largest possible code minimum distance (d.sub.min) for any linear code with the same input (k) and output (n) block length. In this specification, lower case symbols are used to denote variables for the block code and upper case symbols are used to denote variables for the convolutional code. Reed-Solomon coding is well known in the art and a good treatment of the topic is found in a number of references, including "Error Control Coding: Fundamentals and Applications" by S. Lin and D. Costello", Prentice Hall, 1985, pgs. 171-176. In a non-binary code, m bits of data are combined to form a symbol. For an (n,k) Reed-Solomon code, blocks of k data symbols are encoded into blocks of n code symbols called Reed-Solomon code words. The (n,k) Reed-Solomon code is capable of correcting up to (n-k)/2 symbol errors within a block of n symbols. Since n code symbols are transmitted for k data symbols, the code rate, or reduction in the data rate, is k/n.
In a systematic block code, the k data symbols form the first k code symbols of the code word. The n-k parity symbols are formed by a linear combination of the k data symbols according to the generator polynomial g(x). Because of the linear, systematic, and cyclic properties of the Reed-Solomon code, the encoding process is easily achieved with simple shift registers and combinatory logic. The first step in the decoding process involves calculating a set of syndromes from the received n code symbols. The syndromes indicate the location and values of the symbol errors. In particular, the coefficients of the error location polynomial, .sigma.(x), are calculated using the syndromes and from this, the error locators Xi and the error values Yi are computed. With the error locators and error values, the symbols in error are located and corrected.
A rate 1/N convolutional encoder encodes each input bit into N code bits called a code branch according to a set of N generator polynomials. Each generator polynomial G(x) computes one code bit. The N code bits are combined into an N-bit code branch. The constraint length K of the encoder is the number of data bits used in the encoding process and determines the error correcting capability of the code. Long constraint length K yields better performance at the expense of hardware and computational complexity. A state is designated by the K-1 prior input bits and there are 2.sup.K-1 possible states. For each of the 2.sup.K-1 states, a `0` or `1` input bit results in one of two possible code branches. Since each input bit is encoded into N code bits, the code rate for the convolutional encoder is 1/N. Other code rates could be obtained from a 1/N code by puncturing the code bits. Punctured codes are thoroughly treated by J. Cain, G. Clark, and J. Geist in "Punctured Convolutional Codes of Rate (n-1)/n and Simplified Maximum Likelihood Decoding," IEEE Transaction on Information Theory, IT-25, pgs. 97-100, January 1979.
A Viterbi algorithm is used to decode the transmitted code branches at the receiver. A discussion on the theory and operation of the Viterbi decoder is contained in the paper "Convolutional Codes and Their Performance in Communication Systems" by A. Viterbi, IEEE Transaction on Communication Technology, Vol. COM19, no. 5, October 1971, pgs. 821-835. Under certain assumptions about the channel noise, the Viterbi algorithm performs the maximum likelihood decoding of the transmitted data path. For each received code branch, the branch metric of all branches entering each state is computed and added to the corresponding prior path metrics. The best path entering each state is selected and stored as the new path metrics. The selected path is stored in a path memory. In "Development of Variable Rate Viterbi Decoder and its Performance Characteristics," Sixth International Conference on Digital Satellite Communications, Phoenix, Ariz., September 1983, Y. Yasuda et al. show that the survivor paths with the lowest path metric all converge to the same path after a certain chain back depth. Thus, a Viterbi decoded bit is obtained by tracing a path back by at least the chain back distance.
Interleavers and de-interleavers are utilized to combat channel characteristic and to maximize the code effectiveness. In a system in which the channel is not memoryless, bit errors at the receiver occur in bursts. The performance of the Viterbi decoder is better when the Viterbi decoder input contains non-burst type errors. Thus, a de-interleaver before the Viterbi decoder spreads the channel burst errors and `whitens` the errors. Also, a Viterbi decoder has tendency to output bursts of correlated errors in the decoding process. Therefore, a de-interleaver after the Viterbi decoder spreads the burst errors from the Viterbi decoder over different Reed-Solomon code words. The depth of the de-interleaver determines the length of the burst errors which will be successfully handled by the system.
Typically, once a communication system has been designed, data are encoded and transmitted according to the concatenated code. All data bits are encoded and all code bits are transmitted.